/*
 * CVRP.cpp
 *
 *  Created on: 2011-10-30
 *      Author: mateusz
 */

#include <ctime>
#include "NoMatchingCustomer.cpp"
#include "CVRP.h"
#include <cmath>

using namespace std;

// definiton of global variables
extern const int INFTY;
extern Depot* depot;
extern Customers* customers;
extern Parser* p;

vector <int> trace, bestTrace; // vectors with traces
double bestRoute = (double) INFTY, actualRoute = 0, runTime = 0;
time_t startTime;

/**
 * check if time was exceeded
 */
bool timeExceeded() {
	return (time(NULL) - startTime) > runTime;
}

/**
 * calculate distance from p1 to p2
 */
double CVRP::distance(pair <double, double> p1, pair <double, double> p2) {
	double x = sqrt(pow(p1.first - p2.first, 2) + pow(p1.second - p2.second, 2));
	return x;
}

/**
 * calculate directed angle (sin) between p1 and p2
 * add -2 in I quarter, -1 in II, 0 in III and 1 in IV
 */
double CVRP::angle(pair<double, double> p1, pair<double, double> p2){
	double dis = distance(p1, p2);
	return (dis != 0) ? abs(p1.second - p2.second)/dis : 0;
}

/**
 * calculates actual lower bound
 * sum of all min edges left (min edges incident with unvisited customers)
 * + minimum back edge to depot multiplied by minimum numbers of going back to depot
 *
 */
double CVRP::lowerBound() {
	double minEdgesLeft = customers->getMinEdgesLeft(); // sum of all min incident edges from unvisited customers
	double minDepotDistance = customers->getMinVertexDistance(); // min incident edge from all unvisited customers
	int totalDemandLeft = customers->getTotalDemandLeft();
	int vehicleCapacity = depot->getVehicleCapacity();

	return actualRoute + minEdgesLeft + minDepotDistance * ceil(totalDemandLeft / vehicleCapacity);
}

/**
 * build cycle starting from depot
 */

void CVRP::startFromDepot() {
	if (timeExceeded()) {
		throw exception();
	}

	int lastVisited = 0;
	int totalUnvisited = customers->getTotalUnvisitedCustomers();
	Customer* c;
	double vertexDistance;
	pair <double, double> depotXY = depot->getXY();

	// push -1 to trace (depot)
	trace.push_back(-1);

	// if there is any unvisited customer
	if (totalUnvisited) {
		// if final result could be better than actual
		if (lowerBound() < bestRoute) {
			// for each unvisited customer
			while (totalUnvisited--) {
				try {
					// get next unvisited customer and set is as actual (c)
					c = customers->getNextUnvisited(lastVisited, INFTY);
					lastVisited = c->getId() + 1;

					// get distance from depot to actual customer
					vertexDistance = distance(depotXY, c->getXY());

					// increase total actual route
					actualRoute += vertexDistance;

					// go to customer c and build search tree
					buildCycle(c, depot->getVehicleCapacity());

					// after coming back - decrease actual route by the same value
					actualRoute -= vertexDistance;

				}
				// if no unvisited customers left (end of search-tree)
				catch (NoMatchingCustomer &exception) {
					break;
				}

			}
		}
	}
	// if every customer was visited - end of search tree
	else {
		// replace bestTrace and bestRoute, if currently is better
		if (actualRoute < bestRoute) {
			bestRoute = actualRoute;
			bestTrace = trace;
		}
	}

	// remove -1 (depot) from trace
	trace.pop_back();
}

/**
 * continue building cycle starting from customer
 */
void CVRP::buildCycle(Customer* c, int capacityLeft) {
	if (timeExceeded()) {
		throw exception();
	}

	int id = c->getId(), unvisitedLeft = 0;
	double vertexDistance = 0;
	pair <double, double> cXY = c->getXY();
	Customer* c2;

	// visit customer
	customers->visitCustomer(id);
	// push customer id to trace
	trace.push_back(id);
	// decrease vehicle capacity left
	capacityLeft -= c->getDemand();

	// get total unvisited customers
	unvisitedLeft = customers->getTotalUnvisitedCustomers();

	int lastVisited = 0;

	// check lower bound if final result could be better than actual
	if (lowerBound() < bestRoute) {
		// for each unvisited customer
		while (unvisitedLeft--) {
			try {
				// get next unvisited customer
				c2 = customers->getNextUnvisited(lastVisited, capacityLeft);
				lastVisited = c2->getId() + 1;

				// calculate distance between actual customer and chosen next
				vertexDistance = distance(cXY, c2->getXY());

				// increase total route
				actualRoute += vertexDistance;
				// go to customer c2
				buildCycle(c2, capacityLeft);
				// decrease total route
				actualRoute -= vertexDistance;

			}
			// if no unvisited customers left
			catch (NoMatchingCustomer &exception) {
				// get out from while loop
				break;
			}
		}

		// try go to depot
		vertexDistance = distance(cXY, depot->getXY());
		actualRoute += vertexDistance;
		startFromDepot();
		actualRoute -= vertexDistance;

	}
	// unvisit customer
	customers->unvisitCustomer(id);
	// remove customer from trace
	trace.pop_back();
}

/**
 * main CVRP process
 */
void CVRP::process(double seconds) {
	// assign run time
	runTime = seconds;

	// generate all min neighbors distances from each vertex
	customers->preprocessing();

	bestRoute = INFTY;
	actualRoute = 0;
	startTime = time(NULL);

	// start processing
	try {
		startFromDepot();
	}
	// catch time limit exceeded exception
	catch (exception &exception) {
		;
	}

	// write result
	fprintf(p->getSaveFileLink(), "%d %.5lf", (int) count(bestTrace.begin(), bestTrace.end(), -1) - 1,
			bestRoute);
	for (int i = 0; i < (signed) bestTrace.size(); i++) {
		if (bestTrace[i] == -1) {
			fprintf(p->getSaveFileLink(), "\n");
		} else {
			fprintf(p->getSaveFileLink(), "%d ", customers->getCustomerInputId(bestTrace[i]));
		}
	}
}
